package BinaryTree.快排归并;

import BinaryTree.快排归并.ScanUtil.MHUtil_ScanUtil;

/**
 * 快排 - 汉译题
 *   核心：
 *      “前序”
 *      * 先右
 *      汉+题题感 终止 if l>=r
 *
 *   易错：
 *      tmp_l/r
 *      while(1)
 *
 */
/*
  样例：
    10
    293 108 161 783 376 265 330 598 646 812
*/
public class 快排_单点前序 {
    public static void main(String[] args) {
        // n 回车 nums 形式
        MHUtil_ScanUtil.N_NUMS n_nums = MHUtil_ScanUtil.n_enter_nums(" ");
        int n = n_nums.n;
        int[] nums = n_nums.nums;

        quickSort(nums, 0, n - 1);

        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    public static void quickSort(int[] nums, int l, int r) {
        //终止
        if (l >= r) {
            return;
        }

        //暂存
        int lt = l, rt = r;
        //拿头
        int FIR = nums[l];
        //汉:当l<r时交换里面元素
        while (l < r) {
            while (l < r && nums[r] >= FIR) r--;
            int t = nums[r]; nums[r] = nums[l]; nums[l] = t;

            while (l < r && nums[l] < FIR) l++;
            t = nums[r]; nums[r] = nums[l]; nums[l] = t;
        }
        // 前序
        quickSort(nums, lt, l - 1);
        quickSort(nums, l + 1, rt);
    }
}
